package com.itzmn.newcode.offer1;

/**
 * @Author: 张梦楠
 * @Date: 2018/12/18 11:00
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description: 重建二叉树
 *
 *  输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
 *  假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 *  例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，
 *  则重建二叉树并返回。
 *
 *  思路：前序每一个都是根，中序先左再根再右
 *  我们找到根分别左右建树
 *
 */
public class _4_RebuildingBinaryTree {

    public static void main(String[] args) {

        new _4_RebuildingBinaryTree().test();
    }
    public void test(){

        int[] pre = new int[]{1,2,4,7,3,5,6,8};
        int[] in = new int[]{4,7,2,1,5,3,8,6};
        reConstructBinaryTree(pre,in);
    }
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        TreeNode build = build(pre, 0, pre.length - 1, in, 0, in.length - 1);
        return build;
    }
    public TreeNode build(int [] pre,int startPre,int endPre
            ,int [] in,int startIn,int endIn){

        if (startPre>endPre || startIn > endIn){
            return null;
        }
        int rootVal = pre[startPre];

        TreeNode root = new TreeNode(rootVal);

        for (int j=0;j<=in.length;j++){
            if (in[j] == rootVal){
                root.left = build(pre,startPre+1,j+startPre-startIn,in,startIn,j-1);
                root.right = build(pre,j+1+startPre-startIn,endPre,in,j+1,endIn);
                break;
            }
        }
        return root;
    }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
    }
}
